The present invention relates to digital communications, and more particularly to a technique for detecting transmitted data over a communication channel in the presence of finite impulse response (FIR) intersymbol interference (ISI). The invention applies search based decoding methods for channels with FIR-ISI distortion.
Binary Convolutional Codes
In the early days in the field of error control coding, a new technique for encoding was suggested in P. Elias, “Coding for Noisy Channels,” IRE Convention Record, vol. 3, pp. 37-47, 1955. This technique became known as a binary convolutional code (BCC). The idea was to encode binary data by passing the binary message stream through a linear, time invariant, filter with k binary inputs and n>k binary outputs. Linearity, in this case, refers to the fact that the binary alphabet, {0,1}, is a finite field with respect to addition and multiplication modulo 2.
As described in C. Heegard and S. Wicker, Turbo Coding, Kluwer Academic Press, ISBN: 0-7923-8378-8, 1999, there are two general classes of BCC encoders. In the first class, known as finite impulse response (FIR) encoders, each binary output of the encoder is a linear combination of the current k binary inputs and a set of v past inputs. The second class, the infinite impulse response (IIR) BCC encoders, compute the n binary outputs as a function of the current input, past inputs and past outputs. In either case, the encoder can be viewed as a finite state machine (FSM) with k binary inputs, n binary outputs and a state vector of length v. The n binary outputs and the v binary next-state elements are computed as linear combinations of the k binary inputs and the v current-state elements.
An example of an FIR BCC encoder is the 4-state (v=2), (k=1, n=2) BCC described by the equations:cj1=mj⊕mj−2cj2=mj⊕mj−1⊕mj−2or, in terms of a FSM description:cj1=mj⊕sj2cj2=mj⊕sj1⊕sj2sj+11=mjsj+12=sj1
Search Based Decoding
After the advent of BCCs, much effort was expended in developing methods for decoding errors at the receiver in a BCC encoded data stream. Much of the early successful work involved tree searching algorithms, an area that is now commonly known as sequential decoding. In particular, an algorithm known as Fano's Sequential Decoding Algorithm was introduced and has been widely described. Other related algorithms, such as the Stack Algorithm, are techniques for decoding BCC using a search based approach. In these algorithms, the FSM description of the BCC is described as a tree where the nodes of the tree represent the state of the encoder. Branches (directed edges) in the tree are used to describe possible state transitions. The branches are labeled by the k-bit input and n-bit output. A path through the tree describes a concatenated sequence of branches that follow the tree. Associated with each path is an encoding that maps a sequence of k-bit input labels onto a codeword produced by the sequence of n-bit output labels.
Detection of a FSM over a Memoryless Channel
The technique of search based decoding can be applied to the problem of detecting the input sequence to a FSM observed over a memoryless channel. This problem is a central theme in many communications situations and is addressed by methods such as Viterbi decoding and decision feedback equalization. The present invention provides methods and apparatus to enable search-based algorithms to be used to solve the problem.
A memoryless channel is often described in terms of a conditional probability p(y|x) that describes the distribution on the observation variable y conditioned on the input variable x. The channel is memoryless if the output at time j, yj, is independent of the channel inputs and outputs at other times given the input at time j, xj.
In search based decoding, the received sequence is sequentially compared to a path in the tree corresponding to a state sequence of the FSM. Typically, a branch metric is used as a measure of the closeness of the fit between the received symbol and the transition on a given branch. A typical branch metric for a memoryless channel is the log likelihood metric
B(m, s; y)=−log( p(y|x)), where x is the FSM output that corresponds to the input m and the state s. In the case of the additive white Gaussian noise (AWGN), the metric can take the form B(m, s; y)=∥y−x∥2, which describes the energy difference between the input and the output.
Since the transmitted signal is described as a path through the code tree, the accumulated branch metrics along a path through the tree measures the closeness of the received sequence to the codeword described by the path. In search based decoding algorithms, a hypothesized path is rated in terms of the path metric that corresponds to the accumulated branch metrics. As long as the path metric grows as a rate that indicates that the hypothesized path is a reasonable fit, then the path is extended. If the path metric grows at an unacceptable rate, then the search algorithm tries an alternative path. In the case of the Fano algorithm, this involves going back along the current path and trying to find a viable alternative. In the case of stack type algorithms, a list of possible paths is maintained and an alternative path is considered once the current path looks problematic.
In search based decoding, once an error occurs (i.e., the hypothesized path diverges from the path chosen by the encoding of the data at the transmitter), the decoder should soon realize that a wrong turn has been made since it is expected that the path metrics should soon indicate a mismatch has occurred. During the subsequent search of the tree, it is hoped that the error is corrected by the eventual determination of the correct path. This is the essence of search based decoding methods.
Viterbi Decoding
After the advent of sequential decoding for BCCs, Viterbi discovered an optimal method for decoding BCCs over memoryless channels. See A. J. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm,” IEEE Transactions on Information Theory, vol. IT-13, pp. 260-269, April 1967; G. D. Forney, Jr., “The Viterbi Algorithm,” Proceedings of the IEEE, vol. 61, March 1973; C. Heegard and S. Wicker, supra; and S. B. Wicker, Error Control Systems for Digital Communications and Storage, Prentice Hall, 1995. In describing the Viterbi algorithm, Forney showed that the procedure can be described in terms of a trellis description of the code. In the trellis description of a BCC, a bipartite directed graph, called a trellis section, is employed. The trellis section describes one step of the encoding in terms of two complete sets of states. Each state transition allowed by the encoder is described by a branch labeled by the input and output.
The Viterbi algorithm became highly successful for decoding BCCs and other Trellis Codes. In fact it is now common to describe many codes, including linear block codes (LBC), in terms of trellises and Viterbi decoding, as discussed in C. Heegard and S. Wicker, supra.
The Viterbi Algorithm with FIR-ISI Channels
Soon after the discovery of the Viterbi algorithm, it was realized that the algorithm could be applied to other communications problems where the transmission system involves a FSM description. One of the most interesting examples of this approach is a FIR intersymbol interference (ISI) channel with white noise. See, e.g., G. D. Forney, Jr., “Maximum-Likelihood sequence estimation of digital sequences in the presence of intersymbol interference,” IEEE Transactions on Information Theory, vol. IT-18, pp. 363-378, May 1972 and H. Kobayashi, Correlative Level Coding and Maximum Likelihood Decoding,“IEEE Transactions on Information Theory, vol. IT-17, no. 5, pp. 586-594, September 1971. In this model, which models channels with filtering distortion such as multipath, the output of the channel is described as a linear FIR filtering of the input signal followed by a memoryless noise channel. When the input signal set, called the Signal Constellation, is a finite set, then the FIR filter can be expressed as a FSM. It is this realization that led to the application of the Viterbi Algorithm to these communications problems.
The FIR-ISI channel is described in terms of:    1) A finite input signal set or constellation    2) An FIR impulse response, often described by a polynomial h(z)=h0+h1z−1+ . . . hμz−μ of degree μ (the number of terms is μ+1)    3) A noise distribution, variance or correlation.
For example, FIG. 2B illustrates an FIR-ISI channel. The channel input xj takes on values in the QPSK signal set, QPSK={1+i, −1+i, −1−i, 1−i}. There are two multipath terms, that is, the output uj of the FSM 210 depends on a combination of two inputs xj and xj−1 according to uj=Xj+α·xj−1, where α is a complex number referred to as the multipath gain. The final output yj results from the addition of a noise component wj that is complex additive white Gaussian noise with variance σ2. The impulse response in this example, h(z)=1+αz−1, has degree μ=1. In this case, the FIR channel model has four states (xj−1 ∈ QPSK) and a trellis section with 16 branches (xj, xj−1 ∈ QPSK).
Decision Feedback Equalization
A popular, sub-optimal, method for the detection of data over a FIR-ISI channel is known as decision feedback equalization (DFE). The DFE method can be briefly described as a recursive method of determining the path of the FSM that represents the FIR-ISI model of the transmission. The method works as follows. Assume at time j, the DFE has decided the value of the state of the FIR filter, {overscore (s)}j. The DFE detects the value of the current input to the FIR filter. This detection can be achieved by finding the input that optimizes the branch metric B(mj, {overscore (s)}j; yj) over the choices of the input mj. Once the channel input is decided, the value of the state of the FIR filter, {overscore (s)}j+={overscore (s)}j+1, is updated appropriately, based on the decision, and it is not subsequently changed.
Overview of the Present Invention
The present invention provides a new method for the detection of transmitted data over an FIR-ISI channel. The invention can be referred to as a “joint equalization and decoding” receiver solution, and advantageously applies search based decoding methods to channels with FIR-ISI distortion.
A main motivation for the inventive approach was to find an acceptable solution for decoding a FSM in the presence of noise with acceptable complexity. Although the Viterbi algorithm is often an optimal solution, the complexity can be prohibitive. For example, with the Viterbi algorithm, to decode a BCC with memory length v requires a complexity that is proportional to 2k+v; to decode an FIR-ISI channel is proportional to M1+μ where M is the size of the input signal set. Both of these examples demonstrate an exponential dependency, in the memory length, of the complexity of the Viterbi algorithm. Search algorithms, on the other hand, have linear complexity in the memory length.
At the low end of complexity is the DFE. This method is much simpler than Viterbi detection, but can suffer considerable loss especially with a coded transmission system. The DFE approach can be considered as a degenerate form of search-based decoding. The DFE is like a Fano decoder with the alternative to re-examine a decision disabled. In effect, the DFE always moves forward regardless of the quality of the path metric. It is this rigid decision approach that leads to the “error propagation” problem that is often associated with the DFE method. Since a DFE does not use path metric information in the update procedure, this accumulated metric is not computed as part of a DFE.
The present invention is distinct from the DFE approach because, for example, (1) a path metric is used in the detection process and (2) there is a mechanism for reexamining examining a given decision with the intent of correction of possible tentative detection errors.
A preferred extension of the invention is the situation where the data to be transmitted is encoded by a trellis code, such as a BCC or LBC, and transmitted over an FIR-ISI channel. In this case, the transmission process is described in terms of the cascade of two FSMs, the first being the encoder and the latter the FIR-ISI filter. It is an easy exercise to prove that the cascade of two FSMs is itself a FSM where the number of states is at most equal to the product of the number of states of the two FSMs (this is an upper bound on the number of states). See, e.g., P. Elias, supra.
It is interesting to note that the number of states of the cascade, in many practical situations, is less than the upper bound. For example, a (k=1, n=2) BCC with state length v has 2v states, an FIR-ISI channel with μ terms and QPSK inputs has 4μ=22μ states. If the n=2 binary outputs of the BCC are mapped onto QPSK symbols in a one-to-one correspondence and then used as the input to the FIR-ISI channel, then the cascade has 2v+μ states (not 2v+2μ).
More interesting, in the case of search based decoding, is that the tree structure comprises a binary tree and not a 4-ary tree. For example, if a 4-state BCC is combined with a 4-state QPSK-FIR, the result is an 8-state model with a binary tree model.
The invention has been tested in a recent receiver design for a wireless local area network (WLAN) where a coded transmission system is transmitted over a multipath channel which introduces ISI. The coding in use combines BPSK, QPSK or 8-PSK modulation with either a BCC of rate ½ (64-state) or a BCC of rate ⅔ (256-state) or a linear block code known as “CCK” modulation. This receiver has proved to be very effective with a practical implementation complexity.
In the realization of the technique in practice, an estimate of the channel response must be made at the receiver and given to the search based decoder for the detection process. In a packet based system, the estimate can be made on the preamble of the packet and presented to the decoder before the data portion of the packet is to be processed. As an optional extension to the technique, an adaptive equalizer can be used to maintain the validity of the estimated FIR impulse response.
Summarizing,
1) An estimate of the impulse response, {hi}, is obtained;
2) The impulse response and (optionally) the trellis code description is given to the decoder; and
3) The search based decoder detects the data based on the impulse response and (optionally) the trellis code.
An adaptive equalizer can also optionally be used before the decoder to maintain the channel model presented to the decoder.